package org.example.dynamic_planning;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Goal_sum {
    public static int res = 0;

    public static void main(String[] args) {
        //目标和

        //给你一个非负整数数组 nums 和一个整数 target 。
        //向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
        //例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
        //返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
        int[] nums = {100};
        int target = -200;
        int targetSumWays = findTargetSumWays(nums, target);
        System.out.println(targetSumWays);
    }

    //动态规划-01背包
    public static int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum + target) % 2 != 0 || sum+target<0 ) return 0;
        int left = (sum + target) / 2;
        System.out.println(left);
        int[] dp = new int[left + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = left; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[left];
    }

    //回溯算法
    public static int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        int size = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            sum += num;
        }
        if ((sum + target) % 2 != 0) return 0;
        for (int num : nums) {
            if (num != 0) {
                list.add(num);
            } else {
                size++;
            }
        }
        if (sum + target == 0 || sum == 0) {
            return (int) Math.pow(2, size);
        }
        int left = (sum + target) / 2;
        int[] number = list.stream().mapToInt(Integer::intValue).toArray();
        getNumber(number, left, 0, 0);
        return size == 0 ? res : res * (int) Math.pow(2, size);
    }

    public static void getNumber(int[] number, int left, int s, int deep) {
        if (s >= left) return;
        for (int i = deep; i < number.length; i++) {
            s += number[i];
            if (s == left) res++;
            getNumber(number, left, s, i + 1);
            s -= number[i];
        }
    }
}
